/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/*
* Copyright 2010, Center for Advanced Information Systems,Nanyang Technological University
*
* File name: CreateExtendedGraph.java
*
* Abstract: Construct the Spindle Shaped Graph
* Current Version:      0.1
* Auther:               Jin Changjiu
* Modified Date:        June 25,2010
*
*/
package gblend.exactquery;

import gblend.frequentindex.Vertex;
import gblend.infrequentindex.BuildCam;
import gblend.similarity.IdSort;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

/**
 *
 * @author cjjin
 */
public class CreateSpindleGraph {

 private SpindleGraph spigraph = new SpindleGraph(100);
 private int snodeid=0;
 //private BuildCam bc = new BuildCam();
 private Vector<String> levelCamSet = new Vector<String>();//store the unique cams in this graph
 private Queue<SNode> queue = new LinkedList<SNode>();
 
  //Construct the SPIG
  public SpindleGraph constructSPIG(SNode query, SNode seed)
  {
      spigraph.addnode(seed);
      levelCamSet.addElement(seed.getCam());
      queue.offer(seed);
     
      SNode newseed = null;
      while((newseed=queue.poll())!=null)
      {
          Vector<Integer> edgelabelSet = new Vector<Integer>();
          if(newseed.getEnum()==query.getEnum())
          {
              break;
          }

          for(int i = 0; i< newseed.getNnum(); i++)
         {
             
              for(int j = 0; j< query.getNnum(); j++)
              {
                //seed.getNode.getId is the id in query
                int edgelabel= query.getEdge(newseed.getNode(i).getQId(), j);
                if(checkNewedge(newseed,edgelabel,edgelabelSet))
                {
                   //construct a new subgraph based on the seed
                    constructNode(newseed, query, i, j, edgelabel);
                }
              }
         }
    }
      
   return spigraph;

  }

  //8.16 check edgelabel is new for seed
  private boolean checkNewedge(SNode seed, int edgelabel, Vector<Integer> labelset)
  {
    if(edgelabel>0 && !labelset.contains(edgelabel) && !seed.getEdgelabelSet().contains(edgelabel))
    {
        labelset.addElement(edgelabel);
        return true;
    }
    else
    {
        return false;
    }
    
  }


//construct the SPIG nodes based on the supergraphs of the newest edge in Query
  private SNode constructNode(SNode seed, SNode query, int sid, int qid, int edgelabel)
  {
      int nodenum = seed.getNnum();
      int edgenum = seed.getEnum();
      SNode snode = null;
      //test if qid is a node in seed
      int k = seed.getIDsetinQuery().indexOf(qid);
      if(k==-1)
      {
         snode = new SNode(nodenum+1);
      }
      else
      {
         snode = new SNode(nodenum);
      }

      //the Id of node in snode is the Id in query rather than Id in snode
      //copy old nodes and edges from seed
       for(int i=0; i< nodenum; i++)
       {
            Vertex node = new Vertex();
            node.setLabel(seed.getNode(i).getLabel());
            node.setId(i);
            node.setQId(seed.getNode(i).getQId());
            snode.addnode(node);
       }
       snode.setIdSetinQuery(seed.getIDsetinQuery());

       for(int i=0; i< nodenum; i++)
       {
          for(int j=0; j< i; j++)
          {
             int label = seed.getEdge(i, j);
             if(label>0)
             {
                snode.addEdge(i, j, label);
                snode.getNode(i).setDegree();
                snode.getNode(j).setDegree();
                snode.setEdgelabeSet(label);
             }
          }
       }

      if(k==-1)//the node qid doesn't exist in seed, add this node
      {
          Vertex node = new Vertex();
          node.setLabel(query.getNode(qid).getLabel());
          node.setQId(qid);
          node.setId(nodenum);
          snode.addnode(node);
          snode.setIdinQuery(qid);

          snode.addEdge(sid, nodenum, edgelabel);
          snode.getNode(sid).setDegree();
          snode.getNode(nodenum).setDegree();
          snode.setNnum(nodenum+1);
       
      }
      else //else just add edge without adding new node
      {
         snode.addEdge(sid, k, edgelabel);
         snode.getNode(sid).setDegree();
         snode.getNode(k).setDegree();
         snode.setNnum(nodenum);
      }
      //the number of edge always increases
      snode.setEdgelabeSet(edgelabel);
      snode.setEnum(edgenum+1);

      int index = isSameGraph(snode);//check node by its edge label set
      if(index==-1)//check if snode is an new node in exgraph
      {

        String tmpcam = BuildCam.buildCam(snode);
        snode.setCam(tmpcam);
        int t = levelCamSet.indexOf(tmpcam);
        if(t==-1) //if snode's edge label set is unique, and its cam is unique too
        {
           snode.setGraphid(++snodeid);
           spigraph.addnode(snode);
           levelCamSet.addElement(tmpcam);
           spigraph.addEdge(seed.getGraphid()[0], snode.getGraphid()[0]);//exgraph is a directed graph
        }
        else //if snode's cam is not unique, combine it with existing one
        {
          snode.setGraphid(t);
          spigraph.addEdge(seed.getGraphid()[0], t);
        }
        
        queue.offer(snode);
        
        //sort the edge label in label set
        IdSort is = new IdSort();//sort the nodes by label and degree
        Collections.sort(snode.getEdgelabelSet(), is);
      }
      else
      {       
         spigraph.addEdge(seed.getGraphid()[0], index);
      }

      return snode;

  }

//check exnode is a node in SPIG by its edge labels
 private int isSameGraph(SNode exnode)
 {
    for(int i=0; i<spigraph.getSize(); i++)
    {
        if(spigraph.getNode(i).getEdgelabelSet().equals(exnode.getEdgelabelSet()))
        {
            return i;
        }
      
    }
   
    return -1;
 }



}
